package lanQiaoBei.基础算法.sort;
/*
* 归并排序
* */
import java.io.*;
public class P2 {
    static int N;
    static int[]tempArr;
    public static void main(String[] args) throws Exception{
        int[] scan = scan();
        merge_sort(0,N-1,scan);
        for (int i = 0; i < scan.length; i++) {
            System.out.print(scan[i]+" ");
        }
    }

    private static void merge_sort(int l, int r, int[] arr) {
            if(l>=r)return;
            int mid=l+r>>1;
            merge_sort(l,mid,arr);
            merge_sort(mid+1,r,arr);
            int k=0,i=l,j=mid+1;
            while(i<=mid&&j<=r){
                 if(arr[i]<=arr[j])tempArr[k++]=arr[i++];
                 else tempArr[k++]=arr[j++];
            }
            while(i<=mid)
                tempArr[k++]=arr[i++];
            while(j<=r)
                tempArr[k++]=arr[j++];
            for(i=l,j=0;i<=r;i++,j++)
                arr[i]=tempArr[j];
    }

    public static int[] scan() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        tempArr=new int[N];
        String[] s = br.readLine().split(" ");
        for (int i = 0; i <N ; i++) {
            arr[i]=Integer.parseInt(s[i]);
        }
        return arr;
    }
}
